<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /* 暴力法，以每个加油站作为起点，计算开往每个站的剩余油量 */
            /*             var canCompleteCircuit = function (gas, cost) {
                for (let i = 0; i < gas.length; i++) {
                    //开往每个站的剩余油量
                    let rest = gas[i] - cost[i]
                    //下一个站点的下标，因为是环形的，所以最后一个的下一位就是第一位。即(i+1)%数组长度
                    let index = (i + 1) % gas.length
                    while (rest > 0 && index != i) {
                        //模拟以i为起点行驶一圈
                        rest += gas[index] - cost[index]
                        index = (index + 1) % gas.length
                    }
                    //如果跑完一圈且rest>0 那么i就是起点
                    if (rest >= 0 && index == i) return i
                }
                return -1
            } */
            /* 贪心法 */
            var canCompleteCircuit = function (gas, cost) {
                let curSum = 0
                let totalSum = 0
                let start = 0
                for (let i = 0; i < gas.length; i++) {
                    let rest = gas[i] - cost[i]
                    curSum += rest
                    totalSum += rest
                    if (curSum < 0) {
                        start = i + 1
                        curSum = 0
                    }
                }
                //如果最后计算流量总和<0 那么无解
                if (totalSum < 0) return -1
                //如果总和>0 那么一定有解
                return start
            }
        </script>
    </body>
</html>
